// 377. 组合总和 Ⅳ
// 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
// 请你从 nums 中找出并返回总和为 target 的元素组合的个数。
// 题目数据保证答案符合 32 位整数范围。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function (nums, target) {
  const len = nums.length
  const dp = new Array(target + 1).fill(0)

  dp[0] = 1

  // 由于这里寻找的是是由情况，比如 1 1 2 和 1 2 1 是不同情况
  // 所以使用下面的核心框架
  for (let i = 1; i <= target; i++) {
    for (const num of nums) {
      if (num <= i) {
        dp[i] += dp[i - num]
      }
    }
  }

  return dp[target]
}


console.log(
  combinationSum4(
    [9],
    3
  )
)














